package 约瑟夫环;
import java.util.Deque;
import java.util.ArrayDeque;
/**
 * https://blog.csdn.net/u011500062/article/details/72855826 
 * 数学  递推公式的 写法  比较快 但是 不好理解  0 ms
 * 上面 是 数学 方法的 写法
 * 暴力解 比较容易 理解
 * 但时间复杂度  和 空间 复杂度 都 比较高
 * 24 ms 左右
 *但是 能  ac
 */

public class leetcode1823找出游戏的获胜者 {
	public static void main(String []args) {
		System.out.println(solution(11,3));
	}
	static int solution(int n,int k) {
//		int ans = 0;
		Deque<Integer> q = new ArrayDeque<>();
		for(int i = 1;i <= n;i++)
//			q.offer(i);
			q.addLast(i);
		for(int i = 1;i < n;i++) {
//			q.offer(i);
			for(int j = 1;j < k;j++)
//				q.offer(q.poll());
				q.addLast(q.poll());
			q.poll();
		}
	return q.poll();
	}
}
